import java.util.Stack;

public class LeetCode2390 {
    public static void main(String[] args) {
        System.out.println(removeStars1("leet**cod*e"));
    }

    public static String removeStars(String s) {
        StringBuilder result = new StringBuilder();

        Stack<Character> stack = new Stack<Character>();

        char[] chars = s.toCharArray();
        for (char c: chars){
            if(c == '*' ){
                if(!stack.isEmpty()){
                    stack.pop();
                }
                continue;
            }
            stack.push(c);
        }

        while (!stack.empty()){
            result.append(stack.pop());
        }

        return result.reverse().toString();
    }

    public static String removeStars1(String s) {

        StringBuilder ans = new StringBuilder();
        int len = s.length();
        int count = 0;
        char[] ss = s.toCharArray();
        for(int i = len - 1; i >= 0; i--) {
            if(ss[i] != '*' && count == 0) {
                ans.insert(0, ss[i]);
            } else if(ss[i] == '*') {
                count++;
            } else if(ss[i] != '*' && count != 0) {
                count--;
            } else {}   // 防止影响结果
        }
        return ans.toString();
    }

    /**
     * z最优解
     * @param s
     * @return
     */
    public String removeStars3(String s) {
        char[] st=new char[s.length()];
        char[] chars = s.toCharArray();
        int p=-1;
        for (int i=0;i<chars.length;++i){
            if(chars[i]=='*'&&p>=0){
                st[p]=0;p--;
            }else if(chars[i]!='*'){
                p++;st[p]= chars[i];
            }
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<=p;++i){
            sb.append(st[i]);
        }
        return sb.toString();
    }
}
